package main

type Node struct {
	Val   int
	Left  *Node
	Right *Node
	Next  *Node
}

//广度优先搜索
func connect(root *Node) *Node {
	currQueue := []*Node{}
	nextQueue := []*Node{}
	currQueue = append(currQueue, root)
	index := 0
	for index < len(currQueue) {
		if index == len(currQueue)-1 {
			currQueue[index].Next = nil
			if currQueue[index].Left != nil && currQueue[index].Right != nil {
				nextQueue = append(nextQueue, currQueue[index].Left)
				nextQueue = append(nextQueue, currQueue[index].Right)
			}
			currQueue, nextQueue = nextQueue, []*Node{}
			index = 0
			continue
		} else {
			currQueue[index].Next = currQueue[index+1]
			if currQueue[index].Left != nil && currQueue[index].Right != nil {
				nextQueue = append(nextQueue, currQueue[index].Left)
				nextQueue = append(nextQueue, currQueue[index].Right)
			}
			index++
		}
	}
	return root
}

func main() {
	n7 := &Node{Val: 7}
	n6 := &Node{Val: 6}
	n5 := &Node{Val: 5}
	n4 := &Node{Val: 4}
	n3 := &Node{Val: 3, Left: n6, Right: n7}
	n2 := &Node{Val: 2, Left: n4, Right: n5}
	n1 := &Node{Val: 1, Left: n2, Right: n3}
	node := connect(n1)
	println(node)
}
